package LeetCode;

import java.util.Arrays;

/**
 * 逆序对问题
 * 在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。
 * @author Twelve
 */

public class getReverseOrder
{
    public static int sumReverseOrder=0;

    public static void process(int[] arr,int leftNum,int rightNum)
    {
        int midNum = leftNum + ((rightNum-leftNum)>>1);
        if(leftNum==rightNum)
        {
            return;
        }
        process(arr,leftNum,midNum);
        process(arr,midNum+1,rightNum);
        mergeGetReverseOrder(arr,leftNum,midNum,rightNum);
    }
    public static void mergeGetReverseOrder(int[] arr,int leftNum,int midNum,int rightNum)
    {
        int[] res=new int[rightNum-leftNum+1];
        int p1=leftNum,p2=midNum+1,i=0;
        while(p1 <= midNum && p2 <= rightNum)
        {
            //sumReverseOrder+=arr[p1]>arr[p2]?(p2-midNum):0;
            if(arr[p1]>arr[p2])
            {
                sumReverseOrder+=(midNum-p1+1);
                System.out.println("("+arr[p1]+","+arr[p2]+")");
            }
            res[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1 <= midNum)
        {
            res[i++]=arr[p1++];
        }
        while(p2 <= rightNum)
        {
            res[i++]=arr[p2++];
        }
        for(i=0;i<res.length;i++)
        {
            arr[leftNum+i]=res[i];
        }
    }
    public static void main(String[] args)
    {
        /*1~10 长度
          int强制类型转换运算优先级高于乘法
         */
        int[] testArr = new int[(int) (Math.random() * 10) + 1];

        for(int i=0;i<testArr.length;i++)
        {
            testArr[i] = (int) (Math.random() * 100);
        }
        System.out.println(Arrays.toString(testArr));

        process(testArr,0,testArr.length-1);
        System.out.println(sumReverseOrder);
        System.out.println(Arrays.toString(testArr));
    }
}
